The present invention relates to systems and methods for adapting program codes for execution on different computer systems and more particularly to systems and methods for translating codes based on one instruction set to codes based on a relatively reduced instruction set while preserving instruction state-atomicity.
In the early years of computer programming, instructions for computer programs were generated at the microcode level. With the development and growth of software engineering, more tasks were combined in single complex instructions executable by computers having a hardware architecture designed for the instruction complexity.
Increasing instruction complexity generally provided increasing price/performance benefits in the developing environment of computer hardware costs and performance capabilities. As a result, complex instruction set codes (CISC) became widely accepted.
With increased instruction complexity, however, it has become more difficult to design system hardware for higher execution speed. Instead, a reduced instruction set code (RISC), coupled with correlated RISC computer hardware architecture, has gained acceptance as a mechanism to lead to significantly improved system price/performance.
A RISC system generally employs simpler basic instructions to direct desired operations. A single RISC instruction normally specifies a single operation with at most a single memory access. Further, a RISC system normally provides a register for each basic instruction. The instructions in a RISC instruction set are still above the microcode level.
In the typical CISC system, a single instruction may specify a complex sequence of operations and may make many direct accesses to memory. Thus, operations performed by a CISC instruction may require several RISC instructions.
A RISC system is generally designed with optimized hardware and software tradeoffs that provide faster system operation, overall better system performance, and lower system cost relative to available hardware cost and performance capability.
One obstacle to conversion from CISC systems to RISC systems is the existence of large software libraries which have been developed for CISC systems and which are not generally available for RISC systems. When a computer system user chooses to acquire a new computer system, one of the user's major considerations is whether the user's library of application programs can be converted for use on the new computer system, or what the cost of replacing that library would be. Thus, for computer system users who wish to achieve better price/performance through RISC computer systems, it is highly important that an economic and effective mechanism be provided for adapting, or "migrating," the user's library of application programs for execution on the RISC computer system.
Several choices are available to the user for program migration. Recompiling or recoding can be employed, but these techniques are typically used for migrating programs written in a high level language such as FORTRAN and which either have no detailed machine dependencies or have any existing machine dependencies removed by manual programming modifications. Further, in recompiling or recoding, the user typically bears all responsibility for program modification and program behavioral guarantees.
Alternatively, interpretation procedures can be used, but the penalty for this approach typically is substantially reduced program performance.
More particularly, interpretation procedures are software programs that run on one computer and read a stream of subject instructions (which may well be instructions for a different type of computer) as data, and for each subject instruction to perform the indicated operation. Such procedures typically execute 10 to 100 machine instructions on the one computer to interpret a single subject instruction. Thus, interpretation procedures provide substantially reduced program performance, compared to direct execution of functionally-equivalent code on the one computer.
The most effective and efficient migration, however, involves code translation. In code translation, each instruction from an existing program is translated into one or more instructions in the language of the destination machine. Accordingly, a translation of CISC programs to RISC programs, or more generally a program translation in which the translated code has a relatively reduced instruction set, requires "multiple" or "many" instructions in the translated code for each instruction in the code being translated. However, in making "one to many" or CISC-to-RISC code translations, it is generally difficult to preserve many of the instruction behavior guarantees originally provided with the CISC or other relatively complex code.
One normal CISC guarantee that presents some difficulty in translation is the requirement that no other CISC instruction or portion thereof can be executed between the beginning and ending of a single CISC instruction. Accordingly, in translating CISC to RISC it is essential that this type of instruction wholeness or granularity be preserved. Preservation of instruction granularity requires that state or memory atomicity be preserved. Thus, either all memory accesses in an instruction must appear to happen or none must appear to happen in the translated code.
To preserve instruction granularity in the translation process, assurance must be provided that each set, or "granule," of translated instructions corresponding to each more complex instruction will execute to produce the same result that the corresponding more complex instruction would have produced. This must be true even though asynchronous events may occur during execution of any of the "granules" of simpler translated instructions.
The above cross-referenced and concurrently filed patent application Ser. No. 07/666,025 is directed to an invention that provides for the preservation of instruction granularity in code translation and in execution of the translated code. Further, that patent application generally achieves state atomicity and specifically discloses a mechanism and procedure for assuring state atomicity in the case of one-write instructions in the CISC or other code to be translated.
A one-write instruction includes at most one state write that can possibly encounter an exception, but can include an unlimited number of exceptionless state writes. No overlap exists between the two kinds of state writes.
The term "exception" is meant herein to refer to any condition that prevents continuation of the execution of an instruction. Typical exceptions include:
a. memory exceptions such as a page fault or an access violation; PA1 b. arithmetic exceptions such as a floating-point overflow or a divide-by-zero; and PA1 c. instruction exceptions such as an illegal operation code or a breakpoint instruction. PA1 a. a read-modify-write sequence that is "interlocked," or a read-modify-write that requires a partial-memory-word-write and that must be executed on a multiprocessor system with no intervening write by another processor; and PA1 b. multiple state writes that can possibly encounter an exception and must all appear either to happen or not to happen.
State atomicity is equivalent to instruction granularity in the case of a one-write instruction that is translated and executed in accordance with the 1870-0410 patent application. However, other kinds of instructions that must be translated include sequences that present special problems in achieving the preservation of state atomicity and instruction granularity.
Such instructions include those that have:
In these special cases, more particular mechanisms and procedures are needed to address the special circumstances faced while attempting to achieve state atomicity and instruction granularity in the translated code. In the case of instructions having multiple state writes, a state atomicity problem arises where an asynchronous event occurs during execution of an instruction sequence after at least one, and before all of the state (memory or register) writes has been executed. Thus, an exception could occur in one of the translated code instructions remaining to be executed in the sequence such that, if the instruction granule execution is either aborted or continued, a state error may be created since an irreversible state change may already have occurred with the one state write already executed.
In the case of executing translated code on a system having multiple processors with a common memory, a state atomicity problem may arise since a first processor in which the translated code is being executed may partially execute a read-modify-write sequence in an instruction granule, and subsequently, but before the read-modify-write sequence is completed, another processor may write to the state location addressed by the read-write-modify sequence. Again, if the instruction granule execution is either aborted or continued after the conflicting state access by the other processor, a state error may be created since an irreversible state change may already have occurred.
Accordingly, the present invention is directed to structure and procedures for producing and executing translated codes having relatively reduced instruction sets from existing codes having more complex instruction sets while preserving instruction granularity and state atomicity where the codes include instructions involving special circumstances such as multiple or partial writes, interlock instructions, and a multiprocessor execution environment. The present invention thus enables computer system price/performance improvements to be realized while preserving application code investments even in cases where such special circumstances are present.